111. Minimum Depth of Binary Tree

Easy

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

1. Recursion:
   很容易就想到使用递归，但是最开始时对叶子结点的判断方式错了，因为叶子结点应该是not node.right and not node.left，而不是not node。然后每次到达叶子结点就去更新一下最小的depth。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        self.res = float('inf')
        
        def dfs(node, count):
            if not node.right and not node.left:
                self.res = min(self.res, count)
            elif not node.right and node.left:
                dfs(node.left, count+1)
            elif not node.left and node.right:
                dfs(node.right, count+1)
            else:
                dfs(node.left, count+1)
                dfs(node.right, count+1)
        
        dfs(root, 1)
        return self.res

2. BFS

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: return 0
        q = [root]
        level = 1
        while(q):
            L = len(q)
            for i in range(L):
                cur = q.pop(0)
                if not cur.right and not cur.left:
                    return level
                if cur.right: q.append(cur.right)
                if cur.left: q.append(cur.left)
            level += 1
        return level